Presentation and rendering of images and graphics on data processing systems and user terminals, such as computers, and in particular on mobile terminals have increased tremendously the last years. For example, three-dimensional (3D) graphics and images have a number of appealing applications on such terminals, including games, 3D maps and messaging, screen savers and man-machine interfaces.
A 3D graphics rendering process typically comprises three sub-stages. Briefly, a first stage, the application stage, creates several triangles. The corners of these triangles are transformed, projected and lit in a second stage, the geometry stage. In a third stage, the rasterization stage, images, often denoted textures, can be “glued” onto the triangles, increasing the realism of the rendered image. The third stage also performs sorting using a z-buffer.
However, rendering of images and textures, and in particular 3D images and graphics, is a computationally expensive task in terms of memory bandwidth and processing power required for the graphic systems. For example, textures are costly both in terms of memory, the textures must be placed on fast on-chip memory, and in terms of memory bandwidth, a texture can be accessed several times to draw a single pixel.
In order to reduce the bandwidth and processing power requirements, an image (texture) encoding method or system is typically employed. Such an encoding system should result in more efficient usage of expensive on-chip memory and lower memory bandwidth during rendering and, thus, in lower power consumption and/or faster rendering. This reduction in bandwidth and processing power requirements is particularly important for thin clients, such as mobile units and telephones, with a small amount of memory, little memory bandwidth and limited power (powered by batteries).
Delp and Mitchell [1] describe a simple scheme, called block truncation coding (BTC), for image encoding. Their scheme encodes gray scale images by considering a block of 4 pixels×4 pixels at a time. For each such block, two 8-bit gray scale values are generated and each pixel in the block then uses a single bit to index one of these gray scales. This results in a compression rate of 2 bits per pixel (bpp). However, BTC suffers from production of artifacts, above all in regions around edges and in low contrast areas containing a sloping gray level. Furthermore, edges in a gray scale image processed by BTC have a tendency to be ragged.
A simple extension of BTC, called color cell compression (CCC), was presented by Campbell et al. [2]. Instead of using two 8-bit gray scale values for each image block, two 8-bit values are employed as indices into a color palette. This palette comprises 256 colors represented by 8 bits for each of the R, G and B component. An 8-bit index then points at a (24-bit) color in the palette. This allows for compression of images at 2 bpp. However, this does require a memory lookup in the palette. In addition, the palette is restricted in size. The CCC scheme also introduces large color “jaggies” and poorly encodes the case where more than two colors exist in an image block.
In a patent description [3], Iourcha et al. disclose a texture compression scheme called S3TC (S3 Texture Compression) or DXTC (DirectX Texture Compression), that can be seen as an extension of CCC. An image is decomposed into a number of image blocks of 4 pixels×4 pixels. Each such image block is encoded into a bit sequence of 64 bits, thus resulting in a compression rate of 4 bpp. The 64-bit sequence comprises two basic colors or color codewords (16 bits each) and a 32-bit sequence of 2-bit indices, one index for each pixel in the image block. During decoding, a color palette of four colors is generated. The first two RGB (red, green and blue) colors of the palette correspond to the two basic colors (codewords). The two additional colors, situated between the basic colors in the RGB space, are then interpolated therefrom. Each 2-bit index then identifies, for each pixel, one of the four colors of the palette to use for that pixel.
Although, the S3TC scheme works fairly well for computer terminals, it is not well adapted for mobile units and other thin clients. Such mobile units typically only have memory busses of 16 or 32 bits at best. Thus, at least two, and possibly up to four, memory accesses are required to read out the 64-bit compressed version of an image block, if S3TC is implemented in a mobile unit. In addition, during the interpolation of the two additional colors of the color palette, multiplication by ⅓ and ⅔ is performed, which is not ideal in hardware. The compression using S3TC is also relatively time consuming, at least on a mobile terminal.
Akenine-Möller and Ström [4] have developed a variant of S3TC, called POOMA, which is specifically targeted for mobile phones. In POOMA, an image block of 3 pixels×2 pixels is encoded into 32 bits, giving 5.33 bpp. The encoded 32-bit representation of an image block is adapted for the memory busses of mobile phones, which typically are 32 bits at best. Thus, a pixel can be rendered using only one memory access compared to two accesses for S3TC. POOMA uses two base colors but only one additional color interpolated between the base colors, resulting in a color palette of three colors.
A major disadvantage of POOMA is the block size of 3×2 pixels. As a result, calculation of the block address for a particular pixel or texel (texture element) requires division by 3, which is not ideal for hardware design. Furthermore, the widths and heights of textures (images) in graphics are typically always a power of two, which means that a block width of 3 is inconvenient. As for S3TC, the encoding using POOMA is relatively time consuming, in particular when implemented on a mobile terminal.
Fenny [5] discloses an image-encoding scheme used in the MBX graphics hardware platform for mobile phones. This scheme uses two low-resolution images, where one image is usually a low-pass filtered version of the original image. During decoding, a bilinear magnification (upscaling) of these two images is created. Each pixel also stores a blend factor between these two upscaled images. 64 bits are used for encoding each image block and a compression rate of 2 bpp and 4 bpp are described. Information from neighboring image blocks is needed, which complicates decoding.